\subsection{LMT Skeleton and its implementation}
\label{sec:lmtSkeleton}
The goal of the LMT algorithm is to generate a set of edges, called the LMT skeleton, which are definitely part of every minimal triangulation. The algorithm should return a set of edges which belongs to the minimal triangulation and which together form the LMT skeleton. 

The input of the algorithm is a set of points in the plane, called vertices. In this particular case the vertices are randomly generated within a certain range.

The pseudocode of the algorithm the implementation is based on is from \cite{LargeSubgraph} and looks like as follows:

\footnotesize
\begin{enumerate}

\item \emph{candEdges} := A list of empty edges in $S$

\item \emph{edgesIn} := A new empty list

\item Remove convex hull edges from the \emph{candEdges} list and add them to the \emph{edgesIn} list

\item {\bf REPEAT}
	\begin{enumerate}
	\item  {\bf FOR} each edge $e$ $\in$ $candEdges$ {\bf DO}:
	
		 {\bf IF} there does not exist a pair of triangle $t_i$ $\in$ $T_L(e)$ and $t_j$ $\in$ $T_R(e)$ such that $e$ is locally minimal with respect to $t_i$ and $t_j$, and $t_i$ and $t_j$ are both in $candTris$, {\bf THEN} remove $e$ from $candEdges$ and remove all triangles containing $e$ from $candTris$.
		 
 		{\bf END FOR}
  
  
  	 \item  {\bf FOR} each edge $e$ $\in$ $candEdges$ {\bf DO}:
	 
   		  {\bf IF} $e$ intersects no other edge in $candEdges$, {\bf THEN} add $e$ to the $edgesIn$.
   		 
		 {\bf END FOR}
  	 \end{enumerate}

   {\bf UNTIL no more edges change status}
\end{enumerate}
\normalsize
Since the pseudocode is written in an abstract manner, the methods described above did not attempt to optimize the algorithm for speed or recommend the use of complex, efficient data structures. They only serve as a simple description of the algorithm. In order to make the code more efficient and speed up the running time, various optimizations were made and special data structures were used in a later revision of the algorithm. (cf. Sec.\ref{sec:optimization})

The key parts of the implementation in Java are listed below. The algorithm runs in three parts. First of all there is an initialization and generation stage (referred to as stage A). This is followed by a loop that contains two inner loops, referred to as stage B and C.\\\\
The stage A of the algorithm is as follows:
\begin{lstlisting}[caption=Initialisation phase of the LMT Skeleton Algortihm]{Name}
	set.generateTriangles(); // The IndexedFaceSet contains the points
	
	List<Edge> edgesIn = ConvexHullCreator.getHullEdges(set.getCandidateEdges());
	
	for (Edge e:edgesIn) {
		set.removeEdgeButLeaveTriangles(e);
	}
	
	DoublyLinkedList<Edge> edges = set.getCandidateEdges();
	do {
		edgeChanged = false;
			
		// INNERLOOP A runs here
			
		// INNERLOOP B runs here
		
	} while (edgeChanged);
\end{lstlisting}
There are two sub loops running within the outer loop. The first loop A eliminates a number of edges if they are not locally minimal for any triangulation, i.e. these edges are neither contained in this minimal triangulation nor in any other one.
\begin{lstlisting}[caption=Inner loop A of the simple LMT Skeleton algorithm]{Name}
	for (Edge edge : edges) {
		set.removeNonEmptyTrianglesForEdge(edge);
		if  ( ! edge.isDiagonalOfQuadrilateral() ) {
			continue;
		}
				
		if ( ! metric.localMinimumExistsForEdge(edge, set) ) {
			set.removeEdge(edge);
			edgeChanged = true;
	 	} 
	}
\end{lstlisting}
The second inner loop (loop B) selects the valid edges of the minimal triangulation. An edge belongs to the minimal triangulation if and only if it does not intersect any other edge since than it belongs to every possible triangulation that can be constructed with the remaining edges. Notice the "edge.intersects`` method which gets as second parameter the precision to use when calculating intersections. This is necessary because the implementation uses ordinary float datatypes for real values like coordinates. This can cause unpredictable results because of the limited accuracy of binary representation of floating point values. Another approach would be to use the Java BigInteger class which provides accurate floating point arithmetic at the expense of a higher running time per operation.
\begin{lstlisting}[caption=Inner Loop B of the Simple LMT Skeleton Algortihm]{Name}
	for (Edge edge : edges) {
		boolean intersects = false;
		for (Edge otherEdge: set.getCandidateEdges()) {
					
			if (! edge.isAdjacentToEdge(otherEdge)) {
				if (edge != otherEdge && edge.intersects(otherEdge, -0.00001)) {
					intersects = true;
					break;
				}
			}
		}
				
		if (intersects == false) {
			edge.setHighlighted(false);
			edgesIn.add(edge);
			set.removeEdgeButLeaveTriangles(edge); 
			edgeChanged = true;
		}
	}
\end{lstlisting}

To go into the detail of the implementation:\\\\
 {\bf Stage 1}: Triangle generation and convex hull edges
\begin{itemize}
\item In the generation stage all possible edges between all pairs of two vertices within the set are generated and added to a list labeled 'candEdges'. This list always represents all edges that qualify as candidates to be part of the skeleton. As the algorithm proceeds the edges will be eliminated from the candEdges list.

\item Every edge can form a triangle with any other point that exists within the set of points. The next step involves generating a list of triangles from each edge to every other point. For example, an edge with two endpoints A and B can form a triangle with another random point C that exists within the set. There are $\binom{n}{3}$ triangles between $n$ points.

\item Every edge that is on the convex hull of the point set is necessarily part of the LMT skeleton. Therefore all these edges are selected and added to a list $edgesIn$ which will hold all the edges that belong definitely to the LMT skeleton. Afterwards all convex hull edges are removed from the $candEdges$ list.

\item The outer loop, as specified in step 4 above is then executed.\\
\end{itemize}
{\bf Stage 2}: The inner loop A
\begin{itemize}
\item In the first inner loop all remaining candidate edges are considered. Each edge has a number of triangles that are built around it with other points in the set. Only the empty triangles (no points inside them) are of interest. Therefore, all the other triangles are discarded.

\item Every edge needs to have at least two triangles attached to it, implying that the edge needs to be the diagonal of a four sided shape, a quadrilateral. All edges that do not fulfill this property are discarded, too.

\item It can be verified if a specific edge is local minimal related to a quadrilateral. If this edge is not local minimal for all possible quadrilaterals, it will not be in any minimal triangulation and can be removed from the candidate list. To check if an edge is local minimal you consider the quadrilateral around the edge. If this quadrilateral is not convex the edge is local minimal. Otherwise the edge can be flipped, i.e. if $ABCD$ is a quadrilateral and the edge is $\overline{AC}$ you have to consider edge $\overline{BD}$ instead. If the weight regarding to the weight function of the two triangles of the quadrilateral is less than the weight before, the edge was not local minimal.     

\end{itemize}

{\bf Stage 3}: The inner loop B
\begin{itemize}
\item In the second inner loop all remaining edges are considered, too. This loop checks all edges to make sure that they do not intersect with any other edge. 
\item Every edge that remains in the candidate edges list, but does not intersect with any other edge is going to be part of the LMT skeleton since it has to be in every possible triangulation. It is added to the $edgesIn$ collection and removed from the candidate Edges.
%\TODO{Die Dreiecke bleiben drin, denn die beiden anderen Kanten dieser Dreiecke benötigen sie noch für Loop A. Erst wenn alle drei Kanten eines Dreiecks in edgesIn gelandet sind, könnte man es entfernen, aber das würde unnötig Rechenzeit verbrauchen, da nun eh keine Kante mehr da ist, die das Dreieck in Loop A braucht. Wenn in Loop A eine Kante rausfliegt, werden allerdings alle inzidenten Dreiecke ebenfalls gelöscht, da diese Dreiecke nun nicht mehr Teil einer Triangulierung sein können. -nils-}
\item The $edgesChanged$ variable is used to indicate if items were removed or added from the collections. If there was no change in both inner loops, then the outer loop is canceled. Otherwise the outer loop runs again.
\end{itemize}
These three stages represent the implementation of the core algorithm in a straightforward and non-optimized manner in the Java programming language. Since there are $\binom{n}{3}$ possible triangles and every quadrilateral is defined by two triangles chosen from the set of triangles, this implementation has a total running time at least of $O(n^6)$. In further development steps optimized data structures are used to improve the efficiency of the algorithm.
